题目大意

题目链接

有一张 n 个点的完全无向图，点的标号是 1…n，其中边 (i,j) 的长度是 i xor j，现在你需要求出点 1 到点 n 的最短路的长度。

分析

异或的特殊性， 从1 到 n 不论怎么走， 路径的最后一步， 即 某个点 x 到 n 点的距离是 1 ^ n， 让1 ~ n 的路径最小那就让 x为1 就好了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define eps 1e-8

typedef long long ll;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t, n;
    std::cin >> t;
    while(t--){
        std::cin >> n;
        int x = (1 ^ n);
        std::cout << x << "\n";
    }

    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan